/*************************************************************************
	> File Name: 整数的拆分.cpp
	> Author: ma6174
	> Mail: ma6174@163.com 
	> Created Time: Sun 21 Apr 2013 09:50:41 PM CST
 ************************************************************************/

/*
 * 如，对于正整数n=6，可以拆分为：
 * 6
 * 5+1
 * 4+2, 4+1+1
 * 3+3, 3+2+1, 3+1+1+1
 * 2+2+2, 2+2+1+1, 2+1+1+1+1
 * 1+1+1+1+1+1+1
 * 现在的问题是，对于给定的正整数n，程序输出该整数的拆分种类数
 */

#include<iostream>
#include <algorithm>
#include <iterator>
#include <vector>
using namespace std;

/*
 * 功能：计算将一个整数n最多划分成m个数相加，有多少种方法 
 * 参数：  
 *      n: 表示一个待划分的整数
 *      m: 表示最多划分多个个整数相加
 * 示例: IntegerSplit(6, 4) 表示将6拆分成最多4个数之和，有多少种方法
 * 原理：将n拆分成n个1，放分m个格子里，一种情况是格子全满，一种是有空格子
 *       全满的情况下，将所有格子中的1都减少一个，则它等于将(n-m)个1
 *       放入m个格子的情况。
 *       有格子为空的情况下，至少一个格子为空，那么，这种情况下也等于将n个1
 *       放入(m-1)个格子的情况
 *       所以IntegerSplit(n, m) = IntegerSplit(n-m, m) + IntegerSplit(n, m-1)
 *       特殊情况下：
 *       当n < m, 不论怎样放，总有(m-n)个格子为空，等于将n个1放入n个格子里
 *                  则IntegerSplit(n, m) = IntegerSplit(n, n);
 *       当n = m，只有一种情况下格子全满，即所有格子只放一个1
 *                  则IntegerSplit(n, m) = IntegerSplit(n, m-1) + 1;
 */
int IntegerSplit(int n, int m) {
	if (n < 1 || m < 1)
		return 0;
	if (n == 1 || n == 1)
		return 1;

	if (n < m) {
		return IntegerSplit(n, n);
	} else if (n == m) {
		return IntegerSplit(n, m-1) + 1;
	} else {
		return IntegerSplit(n-m, m) + IntegerSplit(n, m-1);
	}
}

void Solution(int sum, vector<int>& vec, int cursum, int k) {
	if (cursum == sum) {
		static int cnt = 1;
		cout << "方案" << cnt++ << ":" << std::endl;
		std::copy(vec.begin(), vec.end(), ostream_iterator<int>(cout, " "));
		std::cout << std::endl;
		return;
	}

	for (int i = k; i <= sum; ++i) {
		if (cursum + i <= sum) {
			vec.push_back(i);
			Solution(sum, vec, cursum + i, i);
			vec.pop_back();
		} else {
			break;
		}
	}
}

int main() {
	std::cout << "整数6的划分种类:" << IntegerSplit(6, 6) << std::endl;
	std::cout << "整数6的划分分别是:" << std::endl;
	vector<int> vec;
	Solution(6, vec, 0, 1);
	return 0;
}
